package com.vincent.exam.tree;

import java.util.ArrayList;
import java.util.Collections;

public class ZLevelOrder {
    private ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    /**
     *
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
        // write code here
        order(root, 0);
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        for(int i =0;i<res.size();i++){
            if(i % 2 == 0){
                list.add(res.get(i));
            } else {
                // 奇数行（从0开始算）需要反转
                Collections.reverse(res.get(i));
                list.add(res.get(i));
            }
        }
        return list;
    }

    /**
     * 层级遍历，这里先左后右
     * @param node
     * @param level
     */
    public void order(TreeNode node, int level){
        if(node == null){
            return;
        }
        if(level == res.size()){
            res.add(new ArrayList<Integer>());
        }
        ArrayList<Integer> list  = res.get(level);
        list.add(node.val);
        if(node.left != null)
            order(node.left, level+1);
        if(node.right != null)
            order(node.right, level+1);

    }
}
